package 每日一题;

import java.util.PriorityQueue;

/**
 * @description:
 * @author: 小白白
 * @create: 2021-05-19
 **/

public class No1738找出第K大的异或坐标值 {

    /**
     * 给你一个二维矩阵 matrix 和一个整数 k ，矩阵大小为 m x n 由非负整数组成。
     * 矩阵中坐标 (a, b) 的 值 可由对所有满足 0 <= i <= a < m 且 0 <= j <= b < n 的元素 matrix[i][j]（下标从 0 开始计数）执行异或运算得到。
     * 请你找出 matrix 的所有坐标中第 k 大的值（k 的值从 1 开始计数）。
     *
     * 示例 1：
     * 输入：matrix = [[5,2],[1,6]], k = 1
     * 输出：7
     * 解释：坐标 (0,1) 的值是 5 XOR 2 = 7 ，为最大的值。
     * 示例 2：
     * 输入：matrix = [[5,2],[1,6]], k = 2
     * 输出：5
     * 解释：坐标 (0,0) 的值是 5 = 5 ，为第 2 大的值。
     * 示例 3：
     * 输入：matrix = [[5,2],[1,6]], k = 3
     * 输出：4
     * 解释：坐标 (1,0) 的值是 5 XOR 1 = 4 ，为第 3 大的值。
     * 示例 4：
     * 输入：matrix = [[5,2],[1,6]], k = 4
     * 输出：0
     * 解释：坐标 (1,1) 的值是 5 XOR 2 XOR 1 XOR 6 = 0 ，为第 4 大的值。
     *  
     * 提示：
     * m == matrix.length
     * n == matrix[i].length
     * 1 <= m, n <= 1000
     * 0 <= matrix[i][j] <= 106
     * 1 <= k <= m * n
     */

    public int kthLargestValue(int[][] matrix, int k) {

        int allLength=matrix.length;
        int itemLength=matrix[0].length;

        PriorityQueue<Integer> priorityQueue=new PriorityQueue<>();

        /**
         * 单:当前横排
         * 终:当前横排^上方的总
         */
        int[][] allDp=new int[allLength][itemLength];

        int num=0;
        //base
        for (int i = 0; i < itemLength; i++) {
            num^=matrix[0][i];
            allDp[0][i]=num;
            if(priorityQueue.size()<k){
                priorityQueue.add(allDp[0][i]);
            }else{
                if(priorityQueue.peek()<allDp[0][i]){
                    priorityQueue.poll();
                    priorityQueue.add(allDp[0][i]);
                }
            }
        }

        for (int i = 1; i < allLength; i++) {
            int itemNum=0;
            for (int j = 0; j < itemLength; j++) {
                itemNum^=matrix[i][j];
                allDp[i][j]=(itemNum^allDp[i-1][j]);
                if(priorityQueue.size()<k){
                    priorityQueue.add(allDp[i][j]);
                }else{
                    if(priorityQueue.peek()<allDp[i][j]){
                        priorityQueue.poll();
                        priorityQueue.add(allDp[i][j]);
                    }
                }
            }
        }

        return priorityQueue.peek();
    }

    public static void main(String[] args) {
        No1738找出第K大的异或坐标值 n=new No1738找出第K大的异或坐标值();
        int[][] arr={{5,2},{1,6}};
        int result = n.kthLargestValue(arr, 4);
        System.out.println(result);
    }

}
